package com.gwl.arithmetic;

public class FindGapOfSeriateArray {

	private static void validateNotEmpty(long[] array) { 
		if(array == null || array.length == 0) { 
			throw new RuntimeException("array is empty"); 
		} 
	}
	private static long findMinElement(long[] array) { 
		validateNotEmpty(array); 
		long minValue = array[0]; 
		for(int i = 1; i < array.length; i++) { 
			if(array[i] == -1L) 
				continue; 
			if(array[i] < minValue) 
				minValue = array[i]; 
		}
		return minValue; 
	} 
	private static long seriateAdd(long minValue, int size) { 
		if(size <= 0) { 
			throw new RuntimeException("size less than zero"); 
		} 
		long total = 0; 
		for(int i = 0; i < size; i++) { 
			total += (minValue + i); 
		} 
		return total; 
	} 
	private static long add(long[] array) { 
		validateNotEmpty(array); 
		long total = 0; 
		for(long i: array) { 
			if(i == -1L) 
				continue; 
			total += i; 
		} 
		return total; 
	} 
	private static long reduce(long seriateProduct, long product) { 
		return seriateProduct - product; 
	}
	
	
	public static long findGap(long[] array) { 
		validateNotEmpty(array); 
		long min = findMinElement(array); 
		long seriateProduct = seriateAdd(min, array.length); 
		long product = add(array); 
		long gap = reduce(seriateProduct, product); 
		return gap; 
	}
	
	public static void main(String[] args) {
		long[] a1= {10, 2, 3, 4, 5, 1, 7, 8, 9, -1}; 
		long[] a2 = {1000001, 1000004, 1000002, -1, 1000005, 1000008, 1000006, 1000009, 1000007}; 
		
		System.out.println(findGap(a1)); 
		System.out.println(findGap(a2)); 
	}

}
